import java.util.ArrayDeque;
import java.util.Deque;

// 定义一个单调队列类
class MonotonicQueue {
    private Deque<Integer> data;

    public MonotonicQueue() {
        data = new ArrayDeque<>();  // 使用 ArrayDeque 来实现双端队列
    }

    // 将元素 n 加入队列中
    public void push(int n) {
        // 将队列中小于 n 的元素都移除，以保持队列的单调递减性质
        while (!data.isEmpty() && data.peekLast() < n) {
            data.pollLast();
        }
        data.offerLast(n);  // 将 n 加入队列的末尾
    }

    // 返回当前队列中的最大值
    public int max() {
        return data.peekFirst();
    }

    // 将元素 n 从队列中移除
    public void pop(int n) {
        if (!data.isEmpty() && data.peekFirst() == n) {
            data.pollFirst();
        }
    }
}

public class Solution {
    // 返回滑动窗口的最大值数组
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue window = new MonotonicQueue();  // 创建一个单调队列
        int[] res = new int[nums.length - k + 1];  // 存储结果的数组
        int resIndex = 0;  // 结果数组的索引

        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {  // 先填满窗口的前 k - 1
                window.push(nums[i]);
            } else {  // 窗口向前滑动
                window.push(nums[i]);  // 将当前元素加入队列
                res[resIndex++] = window.max();  // 将当前窗口中的最大值加入到结果数组中
                window.pop(nums[i - k + 1]);  // 将窗口最左侧的元素从队列中移除
                /*注意，这里移除的这个数是nums[i-k+1]，不是窗口中最左侧的那个最大数*/
            }
        }

        return res;  // 返回结果数组
    }
}